Thực đơn
Thuật_toán_Edmonds–Karp Ví dụXét một mạng gồm bảy đỉnh, đỉnh phát A, đỉnh thu G, và khả năng thông qua được cho trong hình dưới đây:
Trong cặp số f / c {\displaystyle f/c} trên mỗi cung, f {\displaystyle f} là luồng hiện tại, và c {\displaystyle c} khả năng thông qua. Khả năng thông qua còn dư từ u {\displaystyle u} đến v {\displaystyle v} là c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} , hiệu của khả năng thông qua và luồng hiện tại. Nếu luồng từ u {\displaystyle u} đến v {\displaystyle v} là âm, nó làm tăng khả năng thông qua còn dư từ u {\displaystyle u} đến v {\displaystyle v} .
Chú ý là chiều dài đường tăng luồng (màu đỏ) không bao giờ giảm. Đường tăng tìm được luôn là ngắn nhất có thể. Luồng tìm được bằng tổng khả năng thông qua của lát cắt cực tiểu trong đồ thị chia cắt đỉnh phát và đỉnh thu. Có đúng một lát cắt nhỏ nhất trong đồ thị này, chia tập hợp đỉnh thành { A , B , C , E } {\displaystyle \{A,B,C,E\}} và { D , F , G } {\displaystyle \{D,F,G\}} , và có khả năng thông qua
c ( A , D ) + c ( C , D ) + c ( E , G ) = 3 + 1 + 1 = 5. {\displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\ }Thực đơn
Thuật_toán_Edmonds–Karp Ví dụLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ thiên văn học Thuật ngữ lý thuyết đồ thị Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật toán Kruskal Thuật toán sắp xếpTài liệu tham khảo
WikiPedia: Thuật_toán_Edmonds–Karp http://www.cis.upenn.edu/~wilf/AlgComp3.html //doi.org/10.1145%2F321694.321699 https://web.archive.org/web/20061005083406/http://...